New data privacy laws have appeared recently, such as the HIPAA laws for protecting medical records, and the PCI guidelines for protecting credit card information. Data privacy can be defined as maintaining the privacy of Personal Identifiable Information (PII) from unauthorized accessing. PII includes any piece of data that can be used alone, or in conjunction with additional information, to uniquely identify an individual. Examples of such information include national identification numbers, credit card numbers, as well as financial and medical records. Access control methods and data encryption provide a level of data protection from unauthorized access. However, it is not enough—for example, it does not prohibit identity thefts. It was recently suggested that 70% of data privacy breaches are internal breaches that involve an employee from the enterprise who has access to some training or testing database replica, which contains all the PII. Accordingly, in addition to access control, what are needed are techniques to protect such datasets, including preserving the data usability while protecting its privacy. These challenges are further complicated when realtime requirements are added. This is the general area that embodiments of the invention are intended to address.